#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
typedef int Elemtype;
typedef struct LinkNode{
    Elemtype data;
    struct LinkNode *next;
}LinkNode, *LinkList;

int createHead(LinkList *L, int arr[] ,int length){
    (*L) = (LinkNode*)malloc(sizeof(LinkNode));
    LinkNode *pHead = *L;
    pHead->next = NULL;
    int cnt = 0;
    while (cnt < length)
    {
       LinkNode * pNode = (LinkNode*)malloc(sizeof(LinkNode));
       pNode->data = arr[cnt++];
       pNode->next = pHead->next;
       pHead->next = pNode;
    }
    return 1;
}


int createTail(LinkList *L, int arr[] ,int length){
    (*L) = (LinkNode*)malloc(sizeof(LinkNode));
    (*L)->next = NULL;
    LinkNode *pTail = *L;
    int cnt = 0;
    while (cnt < length)
    {
       LinkNode * pNode = (LinkNode*)malloc(sizeof(LinkNode));
       pNode->data = arr[cnt++];
       pNode->next = NULL;
       pTail->next = pNode;
       pTail = pNode;
    }
    return 1;
}

void print(LinkList L){
    LinkNode *pNode = L->next;
    while (pNode!=NULL)
    {
       printf( " %d ",pNode->data);
       pNode = pNode->next;
    }
   printf("\n"); 
}

void deleteNohead(LinkList *L){
    LinkNode *pNode = (*L);
    (*L) = (*L)->next;
    free(pNode);
}

void deleteHavehead(LinkList L){
    if(L->next!=NULL){
        L->next = L->next->next;
    }
}
#define INF -9999999
//递归求最大整数
int max(LinkNode * pNode){
    if(pNode == NULL){
        return INF ;
    }
    int res =  max(pNode->next) > pNode->data ?max(pNode->next):pNode->data;
    return res;
}
//求节点数量
int Nodes(LinkNode * pNode){
    if(pNode == NULL){
        return 0 ;
    }
    int res =  1 + Nodes(pNode->next) ;
    return res;
}

//递归求最大整数
int sum(LinkNode * pNode){
    if(pNode == NULL){
        return 0 ;
    }
    int res =  pNode->data + sum(pNode->next);
    return res;
}
//访问第i个数据节点
LinkNode * findIth(LinkList L,int i){
    int cnt = 0;
    LinkNode *pNode = L;
    while (NULL != pNode->next )
    {
       cnt++;
       if(i == cnt){
            return pNode->next;
       }
       pNode = pNode->next;
    }
}

//在第i个数据节点前插入一个元素e
void insertBeforeIth(LinkList L,int i,Elemtype e){
   int cnt = 0;
   LinkNode *pNode = L;
    while (NULL != pNode->next )
    {
       cnt++;
       if(i == cnt){
           //在pnode后面插入，pnode是i-1的位置
           LinkNode * pNew = (LinkNode*)malloc(sizeof(LinkNode));
           pNew->data = e;
           pNew->next = pNode->next;
           pNode->next = pNew; 
           break; // return;
       }
       pNode = pNode->next;
    }

}   
//求倒数第m个位置节点的值并输出
void getData(LinkList L,int m){
    LinkNode *pCur = L;
    LinkNode *pNode = L;
    int cnt = 0 ; 
    while (pNode!=NULL)
    {
       if(cnt == m){
            break;
       }
       pNode = pNode->next;
       cnt++;
    }
    while (pNode!=NULL)
    {
       pNode = pNode->next;
       pCur = pCur->next;
    }
    printf("the -mth is %d\n",pCur->data);
}
//求第i个元素的前驱节点
LinkNode* getPre(LinkList L,int i){
     int cnt = 0;
    LinkNode *pNode = L;
    while (NULL != pNode->next )
    {
       cnt++;
       if(i == cnt){
            return pNode;
       }
       pNode = pNode->next;
    }
}
//两表移植问题
void operaAandB(LinkList A,LinkList B,int j,int len){
    //增加头结点
     LinkNode * pLa = (LinkNode*)malloc(sizeof(LinkNode));
     LinkNode * pLb = (LinkNode*)malloc(sizeof(LinkNode));
     pLa->next = A;
     pLb->next = B;
    //使用函数求需要用到的前驱节点
    LinkNode * Lapre = getPre(pLa,j);
    LinkNode * Lbpre = getPre(pLb,j);
    LinkNode * LaLast = getPre(pLa,j+len);
    //使用临时变量记录下Ja 
    LinkNode*pNode = Lapre->next;
    //移动
    Lapre->next = LaLast->next;
    LaLast->next = Lbpre->next;
    Lbpre->next = pNode;
    //删除头结点
    print(pLa);
    print(pLb);
    free(pLa);
    free(pLb);
}

//求前半部分和后半部分是否对称
int isSym(LinkList L,int n){
    int cnt = 0;
    LinkNode * pNode = L;
    while (pNode->next!=NULL)
    {
        cnt++;
       if(n/2 == cnt){
            break; // n/2是 pnode->next
       }
       pNode = pNode->next;
    }
    //判断奇偶来决定后面这个指针的位置
    LinkNode* pFront = L->next;
    LinkNode* pLast = NULL;
    if (n%2 == 0)
    {
        pLast = pNode->next->next;
    }else{
         pLast = pNode->next->next->next;
    }
    
    while (pLast!=NULL)
    {
        if(pFront->data != pLast->data){
                return 0;
        }
        pFront = pFront->next;
        pLast = pLast->next;
    }
    return 1;
    
}

//删除非递减重复元素
void deleteSimilar(LinkList L){
    LinkNode * pre = L;
    LinkNode * pCur = L->next;
    while (pCur!=NULL)
    {
        if(pre!=L && pre->data == pCur->data){
            pre->next = pCur->next;
            free(pCur);
            pCur = pre->next;
        }else{
            pre = pCur;
            pCur = pCur->next;
        }
    }
    
}
//非递减，统计小于x的元素个数 
int lessNodes(LinkList L,Elemtype x){
    int cnt = 0;
    LinkNode * pre = L;
    LinkNode * pCur = L->next;  
    while (pCur!=NULL && pCur->data <x)//只需要访问小于x的节点
    {
        if(pre==L || pre->data != pCur->data){
           cnt++;
           pre = pCur;
           pCur = pCur->next;
        }else{
           pCur = pCur->next;
        }
    }
    printf("the num is %d\n",cnt);
    return cnt;
}
//删除非递减单链表La中与非递减Lb相同的元素
void deleteAandBSame(LinkList La,LinkList Lb){
    LinkNode *pre = La;
    LinkNode *paCur = La->next;
    LinkNode *pbCur = Lb->next;
    while (paCur !=NULL && pbCur!=NULL)
    {   //谁小谁移动
       if(paCur->data > pbCur->data){
            pbCur = pbCur->next;
       }else if (paCur->data < pbCur->data)
       {
            pre = paCur;
            paCur = paCur->next;
       }else{
            //相等执行删除操作
            pre->next = paCur->next;
            free(paCur);
            paCur = pre->next;
       }    
    }
}

//递增，在表Lc中删除同时出现在La和Lb中的所有元素
/*
  寻找两个链表中相同的元素
    从Lc中删除
*/
void deleteAandBandCSame(LinkList La,LinkList Lb,LinkList Lc){
    LinkNode *pre = Lc;
    LinkNode *paCur = La->next;
    LinkNode *pbCur = Lb->next;
    LinkNode *pcCur = Lc->next;
    while (paCur !=NULL && pbCur!=NULL && pcCur!=NULL)
    {   //谁小谁移动
       if(paCur->data > pbCur->data){
            pbCur = pbCur->next;
       }else if (paCur->data < pbCur->data)
       { 
            paCur = paCur->next;
       }else{
            //相等,在C表中寻找这个元素，如果有就删除,只用删除一次
            while (pcCur!=NULL && paCur->data >= pcCur->data)
            {//只有c有可能相等再进入循环，如果c大一定不可能相等就没必要循环了
              if(paCur->data == pcCur->data){
                //执行删除
                pre->next = pcCur->next;
                free(pcCur);
                pcCur = pre->next;
                break;
            }
              pre= pcCur;
              pcCur = pcCur->next;  
            }   
            paCur = paCur->next;
            pbCur - pbCur->next;
       }    
    }
}

//去重插入操作  LcNode永远指向最后一个节点，要使用二级指针
void insertTail(LinkList *LcNode ,LinkNode *pNode){
    if((*LcNode)->data == pNode->data){
        return;
    }
    pNode->next = NULL;
    (*LcNode)->next = pNode;
    (*LcNode) = (*LcNode)->next; //这一步就是为什么使用二级指针
}

//将A表和B表合并成C表并去重  1123   122456
void merge(LinkList La,LinkList Lb,LinkList *Lc){
    LinkNode *paCur = La->next;
    LinkNode *pbCur = Lb->next;
    *Lc = La;
    LinkNode * pcCur = *Lc;
    free(Lb);
    while (paCur !=NULL && pbCur!=NULL)
    {   LinkNode *tempNode = NULL;
       if(paCur->data > pbCur->data){
            tempNode = pbCur;
            pbCur= pbCur->next;
            //对C的去重插入操作
            insertTail(&pcCur,tempNode);
       }else if (paCur->data < pbCur->data)
       {
            tempNode = paCur;
            paCur= paCur->next;
            //对C的去重插入操作
            insertTail(&pcCur,tempNode);

       }else{
           tempNode = paCur;//选择插入a节点
           paCur= paCur->next;
           
           LinkNode *tempBNode = pbCur;
           pbCur= pbCur->next; 
           free(tempBNode);//多出来的重复的B节点被释放
           pbCur= pbCur->next; 
           //对C的去重插入操作
           insertTail(&pcCur,tempNode); 
       }    
    }
    while (paCur!=NULL)
    {
       LinkNode *tempNode = paCur;
       paCur= paCur->next;
       //对C的去重插入操作
        insertTail(&pcCur,tempNode);
    }
     while (pbCur!=NULL)
    {
       LinkNode *tempNode = pbCur;
       pbCur= pbCur->next;
       //对C的去重插入操作
       insertTail(&pcCur,tempNode);
    }

}

int main(){
    int a[9] = {1,2,3,4,5,6,7,8,9};
    int b[9] = {1,3,4,5,6,9};
    int c[9] = {1,2,3,5,6,11};
    LinkList La = NULL;
    LinkList Lb = NULL;
    LinkList Lc = NULL;
    createTail(&La,a,9);
    createTail(&Lb,b,6);
   // createTail(&Lc,c,6);
  // print(Lc);
   merge(La,Lb,&Lc);
 //   printf("the res is %d\n",  res);
   print(Lc);
}